package com.platform.modules.alg.alglib.poj3648;

public class Poj3648 {
    private int N = 100010;
    private int a[] = new int[N];
    private node t[] = new node[N << 2];

    private int n;
    private int m;
    private int l;
    private int r;
    long x;

    public String output = "";

    public Poj3648() {
        for (int i = 0; i < t.length; i++) {
            t[i] = new node();
        }
    }

    // 建树
    void build(int x, int l, int r) {
        t[x].l = l;
        t[x].r = r;
        if (l == r) {
            t[x].val = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(x * 2, l, mid);
        build(x * 2 + 1, mid + 1, r);
        t[x].val = t[x * 2].val + t[x * 2 + 1].val;
    }

    // 下传标记
    void pushdown(int x) {
        if (t[x].lazy != 0) {
            t[x * 2].lazy += t[x].lazy;
            t[x * 2].val += t[x].lazy * (t[x * 2].r - t[x * 2].l + 1);
            t[x * 2 + 1].lazy += t[x].lazy;
            t[x * 2 + 1].val += t[x].lazy * (t[x * 2 + 1].r - t[x * 2 + 1].l + 1);
            t[x].lazy = 0;
        }
    }

    // 区间修改
    void update(int x, int l, int r, long num) {
        if (t[x].l == l && t[x].r == r) {
            t[x].val += num * (t[x].r - t[x].l + 1);
            t[x].lazy += num;
            return;
        }
        pushdown(x); // 下传懒标记
        int mid = (t[x].l + t[x].r) >> 1;
        if (r <= mid) {
            update(x * 2, l, r, num);

        } else if (l > mid) {
            update(x * 2 + 1, l, r, num);

        } else {
            update(x * 2, l, mid, num);
            update(x * 2 + 1, mid + 1, r, num);
        }
        t[x].val = t[x * 2].val + t[x * 2 + 1].val;
    }

    // 区间查询
    long query(int x, int l, int r) {
        if (t[x].l == l && t[x].r == r)
            return t[x].val;
        pushdown(x);
        int mid = (t[x].l + t[x].r) >> 1;
        if (r <= mid) {
            return query(x * 2, l, r);

        } else if (l > mid) {
            return query(x * 2 + 1, l, r);

        } else {
            return query(x * 2, l, mid) + query(x * 2 + 1, mid + 1, r);
        }
    }


    public String cal(String input) {
        String[] line = input.split("\n");
        String[] nums = line[0].split(" ");
        n = Integer.parseInt(nums[0]);
        m = Integer.parseInt(nums[1]);
        String[] words = line[1].split(" ");
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(words[i - 1]);
        }

        build(1, 1, n);
        for (int i = 1; i <= m; i++) {
            String[] commands = line[i + 1].split(" ");
            String c;
            c = commands[0];
            l = Integer.parseInt(commands[1]);
            r = Integer.parseInt(commands[2]);

            if (c.charAt(0) == 'Q') {
                output += query(1, l, r) + "\n";
            } else {
                x = Integer.parseInt(commands[3]);
                update(1, l, r, x);
            }
        }

        return output;
    }
}


class node {
    int l;
    int r;
    long val;
    long lazy;
}
